\section{集合}
\subsection{最长连续序列}
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为O(n) 的算法解决此问题。
\begin{Textcode}
	输入：nums = [100,4,200,1,3,2]
	输出：4
	解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
\end{Textcode}
\begin{Mind}{最长连续序列}
	将数组中的元素放入集合，然后挨个取出集合里面的元素，查看x、x+1、x+2、、、x+y是否也存在于集合中，找到的y就是连续序列长度。这么做有一个问题就是，如果是4,3,2,1这组数据，我们找到和4连续的数字有3，同理，我们遍历到3的时候3的相邻依然有4，这样就重复计算了。例如我们可以根据每个数字判断其左边的数据不存在的前提下再进行后续的操作。例如4，我们发现它左边的数字3存在，则不用以它为起点进行统计，因为以3为起点能找到4。同理，当我们找到1之后，我们就开始判断1右边的数字是否存在，然后统计即可。
\end{Mind}

\begin{longlisting}
	\caption{最长连续序列}
	\cppfile[firstline=3,lastline=20]{third_party/coding/cxx/algorithm/common/src/longestConsecutive.cc}
	\label{code:longestConsecutive}
\end{longlisting}
\subsection{单词规律}
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配，例如，pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
\begin{Mind}{单词规律}{}
	将pattern中每个字符映射到s中对应字符串，如果映射中发现了字符对应的串已经存在，但是当前字符串又和存在的字符串不同则返回false。遍历完s和pattern中的字符串之后如果映射中存在不同的key对应相同的value则返回false。
\end{Mind}
核心就是pattern-->s的映射和s-->pattern的映射都需要是一一映射。实现\coderef{code:wordPattern}。
\begin{longlisting}
	\caption{单词规律}
	\cppfile[firstline=16,lastline=43]{third_party/coding/cxx/algorithm/common/src/wordPattern.cc}
	\label{code:wordPattern}
\end{longlisting}
\subsection{找到字符串中所有字母异位词}
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

\begin{Textcode}
	输入: s = "cbaebabacd", p = "abc"
	输出: [0,6]
	解释:
	起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
	起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
	示例 2:

	输入: s = "abab", p = "ab"
	输出: [0,1,2]
	解释:
	起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
	起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
	起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
\end{Textcode}
\begin{Mind}{找到字符串中所有字母异位词}{}
	\begin{itemize}
		\item s如果比p小，则一定找不到异位词。
		\item 循环比较p和s的hash表是否相同，相同则将索引加入。
	\end{itemize}
\end{Mind}
算法实现上可以优化比较。比如s的前三个字符"cba"和p的"abc"相比的hash表都是[1,1,1]所以，很自然0就被加入结果。下一步比较bce和abc。这里有一个技巧，这里s的hash表和p的hash表相同，所以s的hash表可以认为是p的。如果下一步比较的时候比较字符串的第一个元素对hash做一个修改，下一步的一个元素能反向修改回来则认为，他们做了可以相互抵消的修改。这时候下一个元素就能使得结果成立。所以将索引+1加入结果。算法流程如下：
\begin{enumerate}
	\item cba的hash结果为11100和p相同，索引0被加入进结果（最初判断）。
	\item 下一比较的时候当前元素为c，我们对c减去1，滑动引入的元素e加上1，结果变成了[11001]。也就是说滑动将导致e增加的同时c减少了。没有等效抵消的case，滑动后无法得到结果，滑动后索引1无法加入。
	\item 下次比较的时候老b导致b减1，新进入的b导致了b+1，等效抵消，结果[11001]。但是没法抵消e带来的影响，于是2不能作为结果。
	\item 下一比较a和a出于和上面相同的原因，结果[11001],3无法作为结果。
	\item 下一比较老值e消除第二步2的影响，同时b施加影响，结果[12000]，4无法作为结果。
	\item 下一比较老值b导致b减少，新值a导致a增大，结果[21000],5没法作为结果。
	\item 下一步比较老值a减少导致c增加，结果和a相同，6作为结果，如\figref{fig:findAnagrams}。
	\item 最后一步比较老值b减少导致d增加，结果[10110]，7不能作为结果。
\end{enumerate}
\begin{longlisting}
	\caption{找到字符串中的所有字母异位词}
	\cudafile[firstline=3,lastline=24]{third_party/coding/cxx/algorithm/common/src/findAnagrams.cc}
	\label{code:findAnagrams}
\end{longlisting}

\begin{figure}
	\begin{center}
		\includegraphics[width=\textwidth]{findAnagrams}
	\end{center}
	\caption{找到字符串中所有字母异位词}
	\label{fig:findAnagrams}
\end{figure}

\subsection{字母异位词分组}
\begin{example}
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
\end{example}
\begin{Mind}{字母异位词分组}{}
	异位词单词相同顺序不同。如果使用hash表（字符：字符出现的位置）表示则异位词的hash表相同。这里限定了小写字母，所以我们可以使用一个26元素的数组存储字符串中各个字符出现的位置。我们只需要根据hash的位置找到对应的字符串添加到对应的列表中即可。
\end{Mind}
\begin{longlisting}
	\caption{字母异位词分组}
	\cppfile[firstline=3,lastline=18]{third_party/coding/cxx/algorithm/datastruct/src/hash_common.cc}
	\label{code:groupAnagrams}
\end{longlisting}
需要注意的是有Python实现中key必须是可hash的。而Python的List和C++几乎对等，但是List不可hash，需要将List转换为tuple之后才可以hash。
\subsection{赎金信}
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。
\begin{Mind}{赎金信}{}
	统计ransomNote字符出现的频率，如果字符在magazine中不存在则返回false，如果存在且出现频率>ransomNote中的频率返回false。
\end{Mind}
代码实现\coderef{code:canConstruct}
\begin{longlisting}
	\caption{赎金信}
	\cppfile[firstline=7,lastline=24]{third_party/coding/cxx/algorithm/common/src/canConstruct.cc}
	\label{code:canConstruct}
\end{longlisting}
\subsection{存在重复元素 II}
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个\textbf{不同的索引}i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
\begin{Mind}{存在重复元素}{}
	遍历数组，如果元素不在，则将值和其索引存入hash表，如果发现元素存在则拿出索引计算满足abs(i - j) <= k返回true，否则更新索引（更新所以意味着abs(i-j)更小了，更容易<=k）。
\end{Mind}

\begin{longlisting}
	\caption{存在重复元素（索引）}
	\cppfile[firstline=3,lastline=20]{third_party/coding/cxx/algorithm/common/src/containsNearbyDuplicate.cc}
	\label{code:containsNearbyDuplicate}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(n)。
\end{itemize}
\subsection{\href{https://leetcode.cn/problems/QTMn0o/description/}{找到和为k的连续数组}}
\begin{Textcode}
	给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。nums = [1,1,1], k = 2。
\end{Textcode}
其中$1 \leq nums.length \leq 2*10^4$、$-1000 \geq nums[i] \geq 1000$、$-107 \geq k \geq 107$。
\begin{Mind}{找到和为k的连续数组个数}{}
	令 cum[i] 表示从位置 0 到位置 i(不包含位置i)的元素和。cum[i]-cum[j]（j<i）则表示从位置 num[j] 到 num[i-1]的和，如果这个和就是目标则找到和为目标值的区间。
\end{Mind}
以 [3,4,7,2,-3,1,4,2] k = 7为例，我们首先求出cum = [0,3,7,14,16,13,14,18,20]。现在我们只需要找到不同index下相差为7的元素索引即可知道区间和为k的元素个数。比方说cum[2]-cum[0]=7则说明了0-1这两个元素的和为7。cum[3]-cum[2]=7，说明 num[2] =7又找到一个。cum[6]-cum[2]=7又找到一个，最后是cum[8]-cum[5]=7总共找到4个。因为我们需要根据cum快速找到对应的元素，比如cum[8]快速找到cum[5]+7。所以我们把cum存储在hash表里实现O(1)访问。
\begin{longlisting}
	\caption{找到和为k的连续数组}
	\cppfile[firstline=3,lastline=16]{third_party/coding/cxx/algorithm/common/src/subarraySum.cc}
	\label{code:subarraySum}
\end{longlisting}
算法流程：
\begin{enumerate}
	\item 初始化hash表，在cum[0]=1，历史求和结果pre\_sum = 0。
	\item 遍历数组中的每个元素，pre\_sum+=num[i]更新历史求和结果，然后将当前结果存入hash表，将对应的位置+1。
	\item 如果k-pre\_sum已经存在于hash表则有子序列和为sum，count+sum[k-pre\_sum]。
\end{enumerate}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(n)。
\end{itemize}
\subsection{\href{https://leetcode.cn/problems/maximum-sum-circular-subarray/description/?envType=study-plan-v2&envId=top-interview-150}{环形数组的最大和}}
\begin{example}[环形数组的最大和]
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) \% n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 \% n == k2 \% n。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
\end{example}
环形数组意味着有可能数据分段了，所以环形数组最大和有两种情况：
\begin{itemize}
	\item 能求得最大和的数组在数组中间一段。
	\item 能求得最大和的数组在数据两边。
\end{itemize}
对于第一种情况，使用连续数组最大和方法就可以求出。第二种情况结果为数组和减去环形数组最小值。这里简单证明一下第二种情况:
\begin{equation}
	\begin{split}
		max(nums) &= max(left)+max(right)(\text{此时最大值通过算两边数组求得，这是第二种情况的基本假设})\\ 
	left+right &= sum(nums)-mid\\
	max(nums) &= max(sum(nums)-min(mid))
	\label{eq:maxSubarraySumCircular}
	\end{split}
\end{equation}
\ref{eq:maxSubarraySumCircular} 中left表示nums起点[0,i)的求和。mid为[i,j-1)的求和，right表示起点[j:n)元素的求和。同时索引i<j。
\begin{longlisting}
	\caption{环形数组的最大和}
	\cudafile[firstline=3,lastline=17]{third_party/coding/cxx/algorithm/common/src/maxSubarraySumCircular.cc}
	\label{code:maxSubarraySumCircular}
\end{longlisting}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{maxSubarraySumCircular}
	\caption{环形数组的最大和}
	\label{fig:maxSubarraySumCircular}
\end{figure}

\coderef{code:maxSubarraySumCircular} 代码中初始化最小值和最大值，如果只有一个元素则最小值和最大值都是nums[0]，所以初始化为nums[0]。当前最大值的逻辑实际上包含两个逻辑：
\begin{itemize}
	\item 遍历整个数组的时候需要保证第一个元素的时候最大值当前最大值一定是第一个元素，因为 current\_max = 0，所以max(num,current\_max+num) 一定为num。
	\item 如果current\_max+num说明num为负数，这时候也分两种情况：
\begin{enumerate}
	\item current\_max：本身为负数，这时候加上一个负数无疑会让求和更小这时候应该选择num更大的。
	\item current\_num为整数，整数加上负数则结果一定小于正数，选中current\_num。
\end{enumerate}
\end{itemize}
代码中可能会出现max\_value=0的情况，比如[-2,-3,-4]，此时max\_value = -2，此时all\_sum=-9,min\_value=-9，此时all\_sum-min\_value= 0。此时结果应该为-2。

